class Solution {
    public int openLock(String[] deadends, String target) {
        if ("0000".equals(target)) {
            return 0;
        }

        Set<String> deadendSet = new HashSet<>();
        for (String end : deadends) {
            deadendSet.add(end);
        }
        if (deadendSet.contains("0000")) {
            return -1;
        }

        int step = 0;
        Queue<String> queue = new LinkedList<>();
        queue.offer("0000");
        Set<String> used = new HashSet<>();
        used.add("0000");
        while (!queue.isEmpty()) {
            int sz = queue.size();
            // step++; // 1.
            while (sz-- > 0) {
                String status = queue.poll();
                for (String nextStatus : getNext(status)) {
                    if (!used.contains(nextStatus) && !deadendSet.contains(nextStatus)) {
                        if (nextStatus.equals(target)) {
                            // return step; // 1.
                            return step + 1; //2.
                        }
                        queue.offer(nextStatus);
                        used.add(nextStatus);
                    }
                }
            }
            step++; // 2.
        }
        return -1;
    }

    // 枚举 status 通过一次旋转得到的数字
    public List<String> getNext(String status) {
        List<String> ret = new ArrayList<>();
        char[] arr = status.toCharArray();
        for (int i = 0; i < arr.length; ++i) {
            char ch = arr[i];
            // 倒转：0 -> 9
            arr[i] = ch == '0' ? '9' : (char) (ch - 1);
            ret.add(new String(arr));
            // 正转：9 -> 0
            arr[i] = ch == '9' ? '0' : (char) (ch + 1);
            ret.add(new String(arr));
            arr[i] = ch;
        }
        return ret;
    }
}
